package com.sfx.算法专题.正难则反;

/**
 * Created with IntelliJ IDEA.
 * Description:<a href="https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/">...</a>
 * User: sfx
 * Date: 2023-08-05
 * Time: 16:52
 */
public class Code_1_minOperations {

    static class Solution {
        //正难则反
        //我们正面思考,需要左边删除,右边也删除,所以我们可以反面思考
        //找到一个最长的子数组并且和为 sum - x  -->使用滑动窗口即可
        public int minOperations(int[] nums, int x) {
            int left = 0;
            int right = 0;
            int n = nums.length;
            int sum = 0;
            for(int i =0;i<n;++i) sum += nums[i];
            int targrt = sum - x;
            int res = Integer.MIN_VALUE;
            sum = 0;
            while(right < n) {
                sum += nums[right++];
                while(sum > targrt && left < right) {
                    sum -= nums[left++];
                }
                if(sum == targrt)
                    res = Math.max(res,right - left);
            }
            return res == Integer.MIN_VALUE ? -1 : nums.length - res;
        }
    }
}